home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8251 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.3 KB
  1. Path: hubcap.clemson.edu!hubcap!mjs
  2. From: mjs@hubcap.clemson.edu (M. J. Saltzman)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: need psudeo code for binary search
  5. Date: 2 Mar 96 17:26:06 GMT
  6. Organization: Clemson University
  7. Message-ID: <mjs.825787566@hubcap>
  8. References: <Pine.SOL.3.91.960229154211.27358B-100000@obelix> <4h77mu$qtb@news1.cle.ab.com> <313876FF.2403@ix.netcom.com>
  9. NNTP-Posting-Host: hubcap.clemson.edu
  10. X-Newsreader: NN version 6.5.0 #1
  11.  
  12. Norman Bullen <nbullen@ix.netcom.com> writes:
  13.  
  14. >Donald-Anthony C. Phillips wrote:
  15. >> 
  16. >> The binary search algorithm works as follows:
  17. >> 1) Remember the structure must already be sorted.
  18. >> 2) It works better as a recursive function 
  19. >It actually works better when written as a loop because it will use much 
  20. >less stack space.
  21.  
  22. Well, "much less" is relative.  The stack space is proportional to the
  23. log of the size of the list.  In the worst case, invocation to a depth
  24. of 32 calls will be enough to search a list of length 4,294,967,296.  A
  25. depth of 64 will be enough to search a list of length 
  26. 184,467,440,737,009,551,616.
  27.  
  28. Having said that, if you are doing lots of lookups, a loop is likely
  29. to be faster.  On the other hand, the recursion is a tail recursion,
  30. so a good compiler might be able to optimize it away.
  31.  
  32. -- 
  33.         Matthew Saltzman
  34.         Clemson University Math Sciences
  35.         mjs@clemson.edu
  36.